//深度有限遍历
function dfs(node) {
    if (node == null) return;
    console.log(node.value);
    dfs(node.left);
    dfs(node.right);
}

//广度优先遍历
function bfs(node){
    const queue=[node];
    while(queue.length){
        const curr=queue.shift();
        console.log(curr.value);
        if(curr.left) queue.push(curr.left);
        if(curr.right) queue.push(curr.right);
    }
}

//排序算法：快速排序使用分治思想，通过把数组分成较小的块来排序
let index=0
function quickSort(arr){
    if(arr.length<2){
        return arr;
    }
    let pivot=arr[0];   //把第一个假设为中间值
    let left=[];
    let right=[];
    for(let i=1;i<arr.length;i++){
        if(arr[i]<pivot){
            left.push(arr[i]);
        }else{
            right.push(arr[i]);
        }
    }
    console.log("left:",left,"right",right,index++)
    return [...quickSort(left),pivot,...quickSort(right)];
}
let arr=[30,67,3,44,56,7,8,9,3,9,0,4,56,7,8,5,4,2,9]
console.log(quickSort(arr));


// 查找算法
function binarySearch(arr,target){
    let left=0;
    let right=arr.length-1;
    while(left<right){
        const mid=Math.floor((left+right)/2);
        if(arr[mid]===target){
            return mid;
        }else if(arr[mid]<target){
            left=mid+1;
        }else{
            right=mid-1;
        }
    }
    return -1;
}
let arr1=[1,2,3,4,5,6,7,8,9,10];
console.log(binarySearch(arr1,5));


